package sort;


import comment.Comment;

/**
 *create by tbj
 *
 *	1.利用随机的v，随机种子来比较，解决了 近乎排好序的数组。
 *	2.二路排序，解决了含有大量重复的元素，但是也让其偏向了一方
 */
public class QuickSort_Two {
	private static int _partition(int[] a,int l,int r){
		Comment.swapIntArr(a, l, (int)Math.random()*(r-l+1)+l);//优化语句，详情见one
		int v=a[l];
		int i=l+1,j=r;
		while(true){
			while(i <= r && a[i]<v){
				i++;
			}
			while(j >= l+1 && a[j]>v){
				j--;
			}
			if(i > j){ break; }
			
			Comment.swapIntArr(a, i, j);
			i++;
			j--;
		}
		Comment.swapIntArr(a, l, j);
		return j;
	}
	private static void _sort(int[] a,int l,int r){
		if(l >= r){
			return;
		}
		int p=_partition(a,l,r);
		_sort(a, l, p-1);
		_sort(a, p+1, r);
		
	}
	public static void sort(int[] a){
		int n=a.length;
		_sort(a,0,n-1);
	}
	public static void main(String[] args) {
		int[] a=Comment.getRandIntArr(50);
		QuickSort_Two.sort(a);
		for (int i : a) {
			System.out.print(i+" ");
		}
		/*int[] a=Comment.getRandIntArr(500000);
		int[] b=Arrays.copyOf(a, a.length);
		int[] c=Arrays.copyOf(a, a.length);
		int[] d=Arrays.copyOf(a, a.length);
		
		long t1=System.currentTimeMillis();
		MergeSort.sort(a);
		long t2=System.currentTimeMillis();
		System.out.println("MergeSort:"+(t2-t1));
		
		long t3=System.currentTimeMillis();
		QuickSort_One.sort(b);
		long t4=System.currentTimeMillis();
		System.out.println("QuickSort_One:"+(t4-t3));
		
		long t5=System.currentTimeMillis();
		QuickSort_Two.sort(c);
		long t6=System.currentTimeMillis();
		System.out.println("QuickSort_Two:"+(t6-t5));
		
		long t7=System.currentTimeMillis();
		QuickSort_Three.sort(d);
		long t8=System.currentTimeMillis();
		System.out.println("QuickSort_Three:"+(t8-t7));*/
	}
}
